1. Field of the Invention
The present invention relates to the field of digital image processing systems, in particular, unitary transforms performed on these systems. More specifically, the present invention relates to very fast implementation of inverse discrete cosine transform.
2. Related Application
The present application is related to U.S. Pat. No. 5,224,062 filed on Mar. 17, 1992, entitled Method and Apparatus for Fast Implementation of Inverse Discrete Cosine Transform on a Digital Image Processing System Using Optimized Lookup Tables, assigned to the assignee of the present invention, Sun Microsystems, Inc. of Mountain View, Calif.
3. Background
In image processing, an image is typically represented as a continuous mathematical function. The continuous representation is either made deterministically or statistically. In a deterministic representation, the point properties of the image are considered, whereas, in a statistical representation, the average properties of the image are specified.
In a digital image processing system, typically the continuous representation, whether deterministic or statistic, is constructed by spatial sampling of the physical image's intensity, photographic density, or other like measurements. The analog results of spatial sampling in turn are quantized into discrete results that are proportional to the amplitude of the digital system. The image is reconstructed by "inverting" the quantized discrete spatial sampling results.
Additionally, various unitary transforms may be performed before the image is reconstructed by inversion. The transforms are performed to extract features such as brightness from images, reducing bandwidth or reducing dimensionality. Since a sequence of images literally goes through tens of thousands of transforms, the speed in which these transforms can be performed is of critical importance. For example, if a sequence of images is to be displayed at 10 frames per second, each image has a frame size of 320.times.224 pixels divided into 280 macroblocks of 16.times.16 pixels, and each macroblock has 4 (8.times.8) luminance values and 2 (8.times.8) chrominance values, 16,800 inverse transforms (280.times.6.times.10) per second will have to be performed on the transformed image data.
The discrete cosine transform has found widespread application because of its ability to decorrelate highly correlated inputs and the discoveries of efficient implementation techniques. The earliest fast implementation techniques for discrete cosine transform were based on approaches originally developed for fast Fourier transform, in which the periodicity and recursive nature of the underlying basis functions were exploited . Later fast were developed by considering various factorizations of the discrete cosine transform's basis matrix.
The structural similarities of inverse discrete cosine transform to discrete cosine transform has enabled each of the fast implementation techniques for cosine discrete transform to be easily adapted to their dual inverse discrete cosine transform. As a consequence, there has been little concentration on specific formulations of the inverse discrete cosine transform, and the unique statistical properties of the transform domain description of the input sequence has largely been ignored.
Thus it is desirable to develop fast implementation techniques for inverse discrete cosine transform exploiting the unique statistical properties of the input sequence. In the related U.S. Pat. No. 5,224,062 a method and an apparatus for performing inverse discrete cosine transform in image processing that do just that was disclosed. As will be disclosed, the present invention provides a method and an apparatus for performing inverse discrete cosine transform in image processing in an even faster manner.
For further description of image processing, see William K. Pratt, Digital Image Processing, Wiley Interscience, 1978. For further descriptions of fast implementation techniques for discrete cosine transform, see K. R. Rao and P. Yip, Discrete Cosine Transforms: Algorithms, Advantages, Applications, Academic Press, 1990.